// 状态压缩动态规划解决网格填充问题

#include <bits/stdc++.h>
using namespace std;
// 定义常量：最大状态数、最大行数、无穷大值
#define MAXM 130      // 最大状态数（2^7=128）
#define MAXN 10       // 最大行数
#define INF 100000000 // 表示不可行或极大值

// 全局变量定义
int dp[MAXN][MAXM]; // dp[i][S]表示处理到第i行，状态为S时的最小修改次数
int n, m;           // n为行数，m为列数
char c[MAXN][MAXN]; // 存储原始网格

// 计算将第i行设置为状态S时需要修改的点的数量
// S的二进制表示每一位表示对应列的状态，1表示为'.'，0表示为'#'
int Count(int i, int S) {
  int ret = 0; // 修改次数计数
  for (int j = 0; j < m; j++, S = S >> 1) {
    if (c[i][j] == '#' && (S & 1)) {
      // 原始为'#'但当前状态设置为'.'，需要修改
      ret++; // 统计修改的点的数量
    } else if (c[i][j] == '.' && (!(S & 1))) {
      // 原始为'.'但当前状态设置为'#'，这是非法情况
      return INF; // 非法情况直接返回INF
    }
  }
  return ret;
}

// 检查两行状态是否合法（避免出现相邻两行都有连续两个空格的情况）
bool Check(int Sx, int Sy) {
  // x是当前行状态，y是上一行状态
  for (int j = 0; j < m - 1; j++, Sx = Sx >> 1, Sy = Sy >> 1) {
    // 检查是否存在连续两列都是空格的情况
    if ((Sx & 3) == 0 && (Sy & 3) == 0) {
      // 3的二进制是11，&3后为0表示连续两位都是0（即'#'）
      return false; // 存在非法连续空格，返回false
    }
  }
  return true; // 所有相邻列都合法，返回true
}

// 主解决函数
void Solve() {
  // 读取输入：行数和列数
  scanf("%d%d", &n, &m);
  // 读取网格信息
  for (int i = 0; i < n; i++)
    scanf("%s", c[i]);

  int M = 1 << m; // 每一行的状态总数（2^m）

  // 初始化第一行的所有可能状态
  for (int S = 0; S < M; S++)
    dp[0][S] = Count(0, S);

  // 动态规划过程，处理第2到第n行
  for (int i = 1; i < n; i++)
    for (int S = 0; S < M; S++) {
      // 计算当前行设置为状态S时的修改次数
      int cnt = Count(i, S);
      dp[i][S] = INF; // 初始化为极大值

      if (cnt == INF) // 如果当前状态非法，跳过
        continue;

      // 遍历上一行的所有可能状态，寻找最优解
      for (int S_ = 0; S_ < M; S_++)
        if (Check(S, S_)) // 检查与上一行状态是否兼容
          dp[i][S] = min(dp[i][S], dp[i - 1][S_] + cnt);
    }

  // 寻找最后一行的所有可能状态中的最小值作为答案
  int ans = INF;
  for (int S = 0; S < M; S++)
    ans = min(ans, dp[n - 1][S]);

  // 输出结果
  printf("%d\n", ans);
}

int main() {
  int T; // 测试用例数量
  scanf("%d", &T);
  while (T--) // 处理每个测试用例
    Solve();
  return 0;
}